package datastructure.book.tujiesuanfa.queueastack.bean;

import java.util.ArrayList;

/**
 *  最小栈 提供 push ，pop ，top 操作，
 *  并能在常数时间内检索到最小元素的栈
 */
public class MinStack {

    private int[] stack = new int[0];
    private final Node minNode = new Node(0, 0, null);
    private static class Node{
        int val;
        int cnt;
        Node nextNode;

        public Node(int val, int cnt, Node nextNode) {
            this.val = val;
            this.cnt = cnt;
            this.nextNode = nextNode;
        }
    }

    public MinStack() {

    }

    public void push(int x) {
        if (stack.length == 0) {
            stack = new int[]{x};
            minNode.nextNode = new Node(x, 1, null);
            return;
        }
        int[] temp = new int[stack.length+1];
        System.arraycopy(stack,0,temp,1,stack.length);
        temp[0] = x;
        stack = temp;
        Node tempNode = minNode;
        while (true) {
            if (tempNode.nextNode != null) {
                if (tempNode.nextNode.val > x) {
                    tempNode.nextNode = new Node(x, 1, tempNode.nextNode);
                    break;
                } else if (tempNode.nextNode.val == x) {
                    tempNode.nextNode.cnt++;
                    break;
                } else {
                    tempNode = tempNode.nextNode;
                }
            } else {
                tempNode.nextNode = new Node(x, 1, null);
                break;
            }
        }
    }

    public void pop() {
        if (stack.length == 0) {
            return;
        }
        if (stack.length == 1) {
            stack = new int[0];
            minNode.nextNode = null;
            return;
        }
        int popVal = stack[0];
        int[] temp = new int[stack.length-1];
        System.arraycopy(stack,1,temp,0,stack.length-1);
        stack = temp;
        Node tempNode = minNode;
        while (tempNode.nextNode != null) {
            if (tempNode.nextNode.val == popVal) {
                tempNode.nextNode.cnt--;
                if (tempNode.nextNode.cnt == 0) {
                    tempNode.nextNode = tempNode.nextNode.nextNode;
                }
                break;
            } else {
                tempNode = tempNode.nextNode;
            }
        }
    }

    public int top() {
        if (stack.length == 0) {
            return 0;
        }
        return stack[0];
    }

    public int getMin() {
        return minNode.nextNode.val;
    }
}
